NOTE! All algorithms assume  import java.util.*;

LINES INTERSECTING
bool java.awt.geom.Line2D.linesIntersect(x1,y1,x2,y2,X1,Y1,X2,Y2);

DISTANCE FROM POINT TO LINE
java.awt.geom.Line2D.ptLineDist(double X1, double Y1, double X2, double Y2, double PX, double PY) 

ORIENTATION OF POINT WITH RESPECT TO LINE
java.awt.geom.Line2D.relativeCCW(double x1, double y1, double x2, double y2, double px, double py)
//return values:
//1   - the line segment must turn in the direction that takes the positive X axis towards the negative Y axis. In the default coordinate system, counterclockwise.
//-1  - the line segment must turn in the direction that takes the positive X axis towards the positive Y axis. In the default coordinate system, clockwise.
//0   the point lies exactly on the line segment; rare and not useful for determining colinearity because of floating point rounding issues. 

LINE INTERSECTING RECTANGLE
(new Line2D.Double(double x1, double y1, double x2, double y2)).intersects(double x, double y, double w, double h)

GCD
static int gcd(int m,int n) {
	return m%n==0 ? n : gcd(n,m%n);
}

DECIMAL FORMATTING  ahem ERIC BELL
import java.text.*;
DecimalFormat df= new DecimalFormat("0.###");
df.format(3.043543322);
//OR
(new DecimalFormat("0.###")).format(0.34651231);

BINARY SEARCH
Arrays.binarySearch(Object [] array, Object key);

SORT
Arrays.sort(Object [] array);

LIST TO ARRAY
myList.toArray();

ARRAY TO LIST
static List arrayToList(Object[] arr) {
	ArrayList myList = new ArrayList();
	for (Object o : arr)
		myList.add(o);
	return myList;
}

FLOYD WARSHALL    all-pairs shortest path
//To save paths; nextHop must be initialized by nextHop[i][j]=j for each link i->j
static void floyd(int[][] a, int[][]nextHop){
int n = a.length;
for(int k=0; k<n; k++)
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			if(a[i][j] > a[i][k] + a[k][j]){
				a[i][j] = a[i][k] + a[k][j];
				nextHop[i][j]=nextHop[i][k]; //OPTIONAL for storing paths
			}
}
static void printpath(int i, int j, int[][]nextHop){
	System.out.println(i);
	if(i!=j)  printpath(nextHop[i][j],j,nextHop);
}

BREADTH FIRST SEARCH
//Assumes standard adjacency matrix, with -1 not reachable, and anything else reachable. Costs returned in hops, can modify to return true weights.
static int[] BFS(int[][] a, int start){
	Queue q = new LinkedList();
	int[] cost = new int[a.length]; // OPTIONAL
	int[] pred = new int[a.length]; // OPTIONAL, for predecessor graph
	boolean[] already = new boolean[a.length];
	q.add(start);
	already[start]=true;
	while(!q.isEmpty()){
		int u = (Integer)q.poll();
		for(int i = 0; i < a.length; i++){
			if(a[u][i]!= -1 && already[i]== false){ // for weighted graphs add  || cost[i]>cost[u]+cost[i]
				already[i]=true;
				cost[i]=cost[u]+1;	// OPTIONAL for weighted graphs cost[i]+=cost[u]
				pred[i]=u; // OPTIONAL, for predecessor graph
				q.add(i);
			}
		}
	}
	return pred;	//or you can return cost
}

MINIMUM SPANNING TREES
//both using this edge class, kruskal's on a list or array of edges, prims on an adjacency matrix
class Edge implements Comparable{
	public int from;
	public int to;
	public int weight;
	public Edge(int frm, int too, int wait){
		from = frm;
		to = too;
		weight = wait;
	}
	public int compareTo(Object e){
		return weight-((Edge)e).weight;
	}
}
KRUSKAL'S
static List kruskal(int n, Edge[] edges){
	ArrayList mst= new ArrayList(n-1);
	Set[] sets = new TreeSet[n];
	for(int i = 0; i < n; i++){
		sets[i] = new TreeSet();
		sets[i].add(i);
	}
	Arrays.sort(edges);
	for(int i = 0; i < edges.length; i++){
		if(sets[edges[i].from] != sets[edges[i].to]){
			mst.add(edges[i]);
			sets[edges[i].from].addAll(sets[edges[i].to]);
			for(Object o:sets[edges[i].to])
				sets[(Integer)o]=sets[edges[i].from];
		}
	}
	return mst; //or if sets[0].size()!= n, then mst failed
}
PRIM'S
static List prim(int[][] a){
	ArrayList mst = new ArrayList(a.length-1);
	int[] pred = new int[a.length]; //OPTIONAL
	TreeSet q = new TreeSet();
	Set already = new TreeSet();
	q.add(new Edge(0,0,0));
	while(!q.isEmpty() && mst.size()<a.length){
		Edge ed = (Edge)q.pollFirst();
		if(already.contains(ed.to)) continue;
		already.add(ed.to);
		mst.add(ed);
		for(int i=0; i<a.length; i++)
			if(a[ed.to][i]!= -1)
				q.add(new Edge(ed.to,i,a[ed.to][i]));
		pred[ed.to]=ed.from; //OPTIONAL
	}
	mst.remove(0);
	return mst;
}

BELLMAN FORD     single source shortest path
static void belFord(int n, int source, Edge[] edges){
	int[] pred = new int[n]; //OPTIONAL FOR PREDECESSOR LIST
	int[] d = new int[n];
	Arrays.fill(x,Integer.MAX_VALUE/2);
	d[source]=0;
	for(int i=1; i<n; i++)
		for(Edge e: edges){
			if(d[e.to] > d[e.from]+e.weight){
				d[e.to] = d[e.from]+e.weight;
				pred[e.to] = e.from; //OPTIONAL
			}
	for(Edge e: edges) //OPTIONAL for negative weight cycle detection
		if(d[e.to] > d[e.from]+e.weight) //OPTIONAL
			throw new RuntimeException("Negative weight cycle!!"); //OPTIONAL
}

MAX FLOW
/**
 * Finds the maximum flow in a flow network. - wikipedia
 * @param neighbors neighbour lists (not adjacency matrix)
 * @param capacity capacity matrix (must be n by n)
 * @param src source
 * @param sink sink
 * @return maximum flow
 */
public class EdmondsKarp {
    public static int edmondsKarp(int[][] neighbors, int[][] capacity, int src, int sink) {
        int n = capacity.length;
        // Residual capacity from u to v is capacity[u][v] - F[u][v]
        int[][] F = new int[n][n];
        while (true) {
            int[] parent = new int[n]; // Parent table
            Arrays.fill(parent, -1);
            parent[src] = src;
            int[] nodeCapacity = new int[n]; // Capacity of path to node
            nodeCapacity[src] = Integer.MAX_VALUE;
            Queue<Integer> Q = new LinkedList<Integer>();// BFS queue
            Q.offer(src);
LOOP:       while (!Q.isEmpty()) {
                int u = Q.poll();
                for (int v : neighbors[u]) { // if neighbors is adjacency matrix, for(int i=0;i<neighbors.length;i++)if(neighbors[u][i]!=0){
                    if (capacity[u][v] - F[u][v] > 0 && parent[v] == -1) {
                        parent[v] = u; // There is available capacity, and v is not seen before in search
                        nodeCapacity[v] = Math.min(nodeCapacity[u], capacity[u][v] - F[u][v]);
                        if (v != sink)
                            Q.offer(v);
                        else {// Backtrack search, and write flow
                            while (parent[v] != v) {
                                u = parent[v];
                                F[u][v] += nodeCapacity[sink];
                                F[v][u] -= nodeCapacity[sink];
                                v = u;
                            }
                            break LOOP;
                        }
                    }
                }
            }
            if (parent[sink] == -1) { // We did not find a path to sink
                int sum = 0;
                for (int x : F[src])
                    sum += x;
                return sum;
            }
        }
    }
}

PERMUTATIONS AND COMBINATIONS  (list-based)
// ARRAY COMBINATIONS   Prefer list, but if you need array, call list method. :-P
static void combs(Object[] arr) {
	combs(new ArrayList(), arrayToList(arr));
}

// ARRAY PERMUTATIONS   call list method
static void perms(Object[] arr) {
	perms(new ArrayList(), arrayToList(arr));
}

// LIST PERMUTATIONS           start with  perms(new ArrayList(0), myList);
static void perms(List added, List unadded) {
    if (unadded.size() == 0)
        test(added);
    for (int i = 0; i < unadded.size(); i++) {
       added.add(unadded.remove(i));
       perms(added, unadded);
       unadded.add(i, added.remove(added.size() - 1));
    }
}

// LIST COMBINATIONS           start with  combs(new ArrayList(0), myList);
static void combs(List added, List unadded) {
	if (unadded.size() == 0) 
		return;
	added.add(unadded.remove(0));
	test(added); // for all combs and perms, replace with  perms(added.toArray());
	combs(added, unadded);
	Object temp = added.remove(added.size() - 1);
	combs(added, unadded);
	unadded.add(temp);
}

// LIST COMBINATIONS FROM SHORT TO LONG
static void combsFromShortToLong(List myList) {
	for (int length = 1; length <= myList.size(); length++)
		combsOfLength(new ArrayList(0), myList, length);
}
static void combsOfLength(List added, List unadded, int length) {
	List temp = new ArrayList();
	while (!unadded.isEmpty()) {
		added.add(unadded.remove(0));
		if (length == added.size()) // base case
			test(added);
		else
			combsOfLength(added, unadded, length);
		temp.add(added.remove(added.size() - 1));
	}
	unadded.addAll(0, temp);
}

// LIST COMBINATIONS AND PERMUTATIONS
static void combsNperms(List myList) {
    for (int length = 1; length <= myList.size(); length++) 
            cpOfLength(new ArrayList(0), myList, length);
}
static void cpOfLength(List added, List unadded, int length) {
    for (int i = 0; i < unadded.size(); i++) {
        added.add(unadded.remove(i));
        if (length == added.size())
            test(added);
        else 
            cpOfLength(added, unadded, length);
        unadded.add(i, added.remove(added.size() - 1));
    }
}